import java.util.Stack;

public class IsValid {

    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 != 0) return false;
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            char c = chars[i];
            if (c == '{' || c == '[' || c == '(') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                Character pop = stack.pop();
                if (c == ')') {
                    if (pop != '(') return false;
                } else if (c == '}') {
                    if (pop != '{') return false;
                } else {
                    if (pop != '[') return false;
                }
            }
        }
        return stack.isEmpty() ? true : false;
    }
}
